package com.zou.practice.leetcode;

import com.alibaba.fastjson.JSON;

/**
 * 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
 * <p>
 * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
 * <p>
 * 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 * <p>
 * 示例：
 * <p>
 * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
 * 输出：7 -> 0 -> 8
 * 原因：342 + 465 = 807
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/add-two-numbers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author zouyaowen
 * @date 2020-08-31
 */
public class AddTwoNumbers02 {
    public static void main(String[] args) {
        ListNode l1 = new ListNode();
        l1.val = 2;
        ListNode listNode12 = new ListNode();
        listNode12.val = 4;
        ListNode listNode13 = new ListNode();
        listNode13.val = 3;

        //构建关系
        l1.next = listNode12;
        listNode12.next = listNode13;

        ListNode l2 = new ListNode();
        l2.val = 5;
        ListNode listNode22 = new ListNode();
        listNode22.val = 6;
        ListNode listNode23 = new ListNode();
        listNode23.val = 4;

        //构建关系
        l2.next = listNode22;
        listNode22.next = listNode23;
        System.out.println(JSON.toJSONString(l1));
        System.out.println(JSON.toJSONString(l2));
        ListNode listNode = addTwoNumbers_Solution2(l1, l2);
        System.out.println(JSON.toJSONString(listNode));

    }

    /**
     * 优化版本:1)使用虚拟头结点避免头结点特殊处理
     * 2)链表循环游标变量不能是固定返回值，需要在循环之外定义
     *
     * @param l1 链表一
     * @param l2 链表二
     * @return 结果链表
     */
    private static ListNode addTwoNumbers_Solution2(ListNode l1, ListNode l2) {
        ListNode dummyNode = new ListNode(0);
        ListNode curr = dummyNode;
        int nextExtraData = 0;
        while (l1 != null || l2 != null) {
            int sum = (l1 != null ? l1.val : 0) + (l2 != null ? l2.val : 0) + nextExtraData;
            curr.next = new ListNode(sum % 10);
            nextExtraData = sum / 10;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
            curr = curr.next;
        }
        if (nextExtraData > 0) {
            curr.next = new ListNode(nextExtraData);
        }
        return dummyNode.next;
    }

    /**
     * 逆序列表翻转计算后求和 暴力手段:使用小学加减乘除处理
     * <p>
     * 342
     * +456
     * 807
     * 时间复杂度 O(n)
     *
     * @param l1 链表一
     * @param l2 链表二
     * @return 求和结果计算比逆序新的链表输出
     */
    public static ListNode addTwoNumbers_Solution1(ListNode l1, ListNode l2) {
        ListNode resNode = new ListNode();
        ListNode nextNode = null;
        Integer nextExtraData = 0;
        while (l1 != null || l2 != null) {
            int firstData = l1 != null ? l1.val : 0;
            int secondData = l2 != null ? l2.val : 0;
            int sum = firstData + secondData + nextExtraData;
            nextExtraData = 0;
            if (sum > 9) {
                nextExtraData++;
                sum = sum - 10;
            }
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
            //特殊处理头结点
            if (resNode.next == null) {
                resNode.val = sum;
                if (l1 != null || l2 != null) {
                    nextNode = new ListNode();
                    resNode.next = nextNode;
                }
                // 处理进位数字
                if (l1 == null && l2 == null && nextExtraData > 0) {
                    resNode.next = new ListNode(nextExtraData);
                }
            } else {
                nextNode.val = sum;
                if (l1 != null || l2 != null) {
                    nextNode.next = new ListNode();
                    nextNode = nextNode.next;
                }
                // 处理进位数字
                if (l1 == null && l2 == null && nextExtraData > 0) {
                    nextNode.next = new ListNode(nextExtraData);
                }
            }
        }
        return resNode;
    }
}
